#!/usr/bin/env python

## first, the axioms


def quote(x):
    return [x]

def atom(x):
    if x==[]:
        return "t"
    if type(x)!=type([]):
        return "t"
    else:
        return []

def eq(x,y):
    if x==y:
        return "t"
    else:
        return []

def car(x):
    if type(x)==type([]) and len(x)>0:
        return x[0]
    else:
        return []

def cdr(x):
    if type(x)==type([]) and len(x)>0:
        return x[1:]
    else:
        return []

def cons(x,y):
    if type(y)==type([]):
        z=[x]
        z.extend(y)
        return z
    else:
        return [x]

def cond(*x):
    for i in x:
        if i[0]=="t":
            return i[1]

## the Lemma

def caar(x):
    return car(car(x))

def cadr(x):
    return car(cdr(x))

def caddr(x):
    return car(cdr(cdr(x)))

def cdar(x):
    return cdr(car(x))

def list(x,y):
    
    """this one is somewhat strange
    t=[]
    for i in x:
        t.append(i)
    return t"""
    return cons(x,cons(y,[]))

def null(x):
    return eq(x,[])

def and_(x,y):
    return cond(
        (x, cond( (y,"t"),
                  ("t",[]))),
        ("t",[]))

def not_(x):
    return cond( (x,[]),("t","t"))


def cadar(x):
    return car(cdr(car(x)))
def caddr(x):
    return car(cdr(cdr(x)))
def caddar(x):
    return car(cdr(cdr(car(x))))



## principal!!
env=[[]]

class lisp_exception(Exception):
    pass

class lfs_eval:
    def __init__(self,env=[{}],trace=0):
        self.env=env
        self.trace=trace
    def __call__(self, x):
        return self._call(x)
    def assoc(self,x):
        try:
            for i in xrange(len(self.env)-1,-1,-1):
                if self.env[i].has_key(x):
                    return self.env[i][x]
        except:
            pass
#        print "assco:",x,self.env
        raise lisp_exception, "assoc: undefined symbol: %s"%(x)
        return []
    def push_env(self, x):
        if type(x)==(type({})):
            self.env.append(x)
    def pop_env(self):
        return self.env.pop()
    
    def evcon(self,x):
        for i in x:
            if self._call(i[0])=="t":
                return self._call(i[1])
    def evlis(self,x):
        if null(x)=="t":
            return []
        else:
            return cons(self._call(car(x)),self.evlis(cdr(x)))
    
    def pair(self,x,y):
        for i in xrange(len(x)):
            try:
                self.env[-1][x[i]]=y[i]
            except:
                self.env[-1][x[i]]=[]

    def _call(self, x):
        self.push_env({})
        if self.trace>0:
            print "\n","  "*(len(self.env)-1),"X: ",x,
        if self.trace>1:
            print "\n","  "*(len(self.env)-1),"Env: ",self.env[-1],
        if self.trace>2:
            print "\n","  "*(len(self.env)-1),"   EnvAll: ",self.env[:-1]

        if atom(x)=="t":
            _r=self.assoc(x)
        elif atom(car(x))=="t":
            if car(x)=="quote":
                _r=cadr(x)
            elif car(x)=="echo":
                _r=self._call(cadr(x))
                print unpars(_r)
                
            elif car(x)=="atom":
                _r=atom(self._call(cadr(x)))
            elif car(x)=="eq":
                _r=eq(self._call(cadr(x)),self._call(caddr(x)))
            elif car(x)=="car":
                _r=car(self._call(cadr(x)))
            elif car(x)=="cdr":
                _r=cdr(self._call(cadr(x)))
            elif car(x)=="cons":
                _r=cons(self._call(cadr(x)),self._call(caddr(x)))
            elif car(x)=="cond":
                _r=self.evcon(cdr(x))
            elif car(x)=="define":
                self.env[-2][cadr(x)]=caddr(x)
                _r=caddr(x)
            else:
                _r=self._call(cons(self.assoc(car(x)),cdr(x)))
        elif caar(x)=="label":
            self.env[-1][cadar(x)]=car(x)
            _r=self._call(cons(caddar(x),cdr(x)))
        elif caar(x)=="lambda":
            self.pair(cadar(x),self.evlis(cdr(x)))
            _r=self._call(caddar(x))
        else:
            print "error:",x
            _r=[]
        self.pop_env()
        if self.trace>0:
            print "\n","  "*(len(self.env)),"Return",
            if self.trace>1:
                print "of '",car(x),"'",
            print "is:",_r
        return _r
        
import shlex            
class pars:
    def __init__(self,trace=0):
        self.npar=0
        self.list=[]
        self.stack=[]
        self.last=self.list
        self.eval=lfs_eval(trace=trace)


    def _tokenize(self,l):
        """ 
        tokenlize the line using "(" ")" "'" and "spaces"
        """
        _t=""
        _tl=[]
        sawquote=0
        for i in l:
            if i=="(":
                _tl.append(i)
            elif i==")":
                if _t!="":
                    _tl.append(_t)
                    _t=""
                _tl.append(i)
                
            elif i=="'":
                _tl.append("'")
            elif i in [" ","\t","\n"]:
                if _t!="":
                    _tl.append(_t)
                    _t=""
            else:
                _t+=i
        return _tl
    
    def eat_line(self,l):
        _l=self._tokenize(l)
        for i in _l:
            if i=="(":
                self.last.append([])
                self.stack.append(self.last)
                self.last=self.last[-1]
                self.npar+=1
            elif i==")":
                self.last=self.stack[-1]
                self.stack=self.stack[0:-1]
                self.npar-=1
            else:
                self.last.append(i)
        
    def parse(self,f):
        for i in f.readlines():
            self.eat_line(i)
    def parse_string(self,s):
        self.eat_line(s)

    def exe(self):
        eval=self.eval
        if self.npar==0:
            return eval(self.list[0])
    
    def exeall(self, rfun=None):
        eval=self.eval
        if rfun==None:
            def pr(x):
                print unpars(x)
            rfun=pr
        if self.npar==0:
            for i in self.list:
                rfun(eval(i))
        
def unpars(l):
    if l==[]:
        return "()"
    elif l==None:
        return "()"
    elif type(l)!=type([]):
        return "%s"%l
    else:
        s="("
        for i in l:
            s+=unpars(i)+' '
        s+=")"
        return s

def test():
    e=pars()
    
    r=e.parse_string("""

(cdr 
   (quote (a b c d)))
(cons 
    (quote x) (quote ()))

((lambda (x) (cons x (quote ()))) (quote hgf))
((lambda (x y) (cons x y)) (quote 1) (quote (a b)))

""")
#    print e.list
#    print unpars(e.list)
        
             
    e.exeall()
                     

def main():
    import sys
    import getopt
    opts,args=getopt.getopt(sys.argv[1:],"d:")
    tl=0
    for i in opts:
        if i[0]=="-d":
            try:
                tl=int(i[1])
            except:
                tl=1
                
    if len(args)>0:
        f=file(args[0],"r")
    else:
        f=sys.stdin
    e=pars(trace=tl)
    l=f.read()
    e.parse_string(l)
    rf=lambda x:x
    e.exeall(rfun=rf)

if __name__=="__main__":
    main()
